package Test;

/**
 * @author Chen Yuan
 * @create 2021-04-26  11:04
 */
//=================== 平衡二叉树 ===================================================
public class Tools {
	// 插入一个值，且保持是一个平衡二叉树
	public TreeNode createBST(int value, TreeNode root) {
		if (value < root.val) {
			if (root.left == null) {
				root.left = new TreeNode(value);
			} else {
				createBST(value, root.left);
			}
		} else {
			if (root.right == null) {
				root.right = new TreeNode(value);
			} else {
				createBST(value, root.right);
			}
		}
		if (getTreeHeight(root.left) - getTreeHeight(root.right) > 1) {
			if (root.left != null &&
					getTreeHeight(root.left.left) < getTreeHeight(root.left.right)) {
				leftRotate(root.left);
			}
			rightRotate(root);
		}
		if (getTreeHeight(root.right) - getTreeHeight(root.left) > 1) {
			if (root.right != null &&
					getTreeHeight(root.right.left) > getTreeHeight(root.right.right)) {
				rightRotate(root.right);
			}
			leftRotate(root);
		}
		return root;
	}

	// 通过根节点获得二叉树高度
	public int getTreeHeight(TreeNode root) {
		if (root == null) {
			return 0;
		}
		return Math.max(root.left == null ? 0 : getTreeHeight(root.left),
				root.right == null ? 0 : getTreeHeight(root.right)) + 1;
	}

	// 左旋转
	public void leftRotate(TreeNode root) {
		TreeNode newNode = new TreeNode(root.val);
		newNode.left = root.left;
		newNode.right = root.right.left;
		root.val = root.right.val;
		root.left = newNode;
		root.right = root.right.right;

	}

	// 右旋转
	public void rightRotate(TreeNode root) {
		TreeNode newNode = new TreeNode(root.val);
		newNode.right = root.right;
		newNode.left = root.left.right;
		root.val = root.left.val;
		root.left = root.left.left;
		root.right = newNode;
	}

}

//================== 二叉树 ====================================================

class BinaryTree {

	private TreeNode root;

	public TreeNode getRoot() {
		return root;
	}

	/**
	 * 通过数组创建一个平衡二叉树
	 *
	 * @param array 数组
	 * @param index 指向处理到数组中第几个数
	 * @return
	 */
	public TreeNode createBinaryTreeByArray(int[] array, int index) {
		TreeNode tn = null;
		if (index < array.length) {
			Integer value = array[index];
			if (value == null) {
				return null;
			} else if (value == -1) {
				return null;
			}
			tn = new TreeNode(value);
			tn.left = createBinaryTreeByArray(array, 2 * index + 1);
			tn.right = createBinaryTreeByArray(array, 2 * index + 2);
			return tn;
		}
		return tn;
	}

	// 中序遍历
	public void infixOrder(TreeNode root) {
		if (root == null) {
			return;
		}
		root.infixOrder();
	}

	//添加节点
	public void addNode(TreeNode node) {
		if (root == null) {
			//为空树
			root = node;
		} else {
			root.addNode(node);
		}
	}
}

//================ 树的节点对象 =====================================================

class TreeNode {
	public int val;
	public TreeNode left, right;

	public TreeNode(int val) {
		this.val = val;
		this.left = this.right = null;
	}

	//添加节点
	public void addNode(TreeNode node) {
		if (node == null) {
			return;
		}

		//判断传入的节点的值，和当前子树的根节点的值的关系
		if (node.val < this.val) {
			if (this.left == null) {
				//若当前节点，左子节点为空
				this.left = node;
			} else {
				//若不为空，递归
				this.left.addNode(node);
			}
		} else {
			if (this.right == null) {
				//若当前节点，左子节点为空
				this.right = node;
			} else {
				//若不为空，递归
				this.right.addNode(node);
			}
		}
	}

	//中序遍历
	public void infixOrder() {
		if (this.left != null) {
			this.left.infixOrder();
		}
		System.out.print(this.val + "  ");
		if (this.right != null) {
			this.right.infixOrder();
		}
	}

	@Override
	public String toString() {
		return "TreeNode222{" +
				"val=" + val +
				'}';
	}
}

//====================================================================
////创建二叉排序树


/*
 for (int i = 0; i < array.length; i++){
 binarySortTree.addNode(new TreeNode(array[i]));
 }
*/


class BinarySortTree {
	private TreeNode root;

	public TreeNode getRoot() {
		return root;
	}

	public TreeNode createBinarySortTree(int[] array, int index) {
		TreeNode root = new TreeNode(array[index]);
		this.addNode(root);
		if (index < array.length - 1) {
			createBinarySortTree(array, index + 1);
			return root;
		} else {
			return null;
		}
	}

	//添加节点
	public void addNode(TreeNode node) {
		if (root == null) {
			//为空树
			root = node;
		} else {
			root.addNode(node);
		}
	}

	//中序遍历
	public void infixOrder() {
		if (root != null) {
			root.infixOrder();
			System.out.println();
		} else {
			System.out.println("树为空");
		}
	}

}

//============== 链表 =====================================================
class ListNode {
	int val;
	ListNode next;

	ListNode(int x) {
		val = x;
		next = null;
	}


	@Override
	public String toString() {
		return "<" +
				"val=" + val +
				", " + next +
				'>';
	}
}

class MyList {
	public ListNode createList(int[] array) {
		if (array == null) {
			return null;
		}
		ListNode root, head = new ListNode(array[0]);
		root = head;
		for (int i = 1; i < array.length; i++) {
			head.next = new ListNode(array[i]);
			head = head.next;
		}
		return root;
	}
}

//=============================================================
class Interval {
	int start, end;

	Interval(int start, int end) {
		this.start = start;
		this.end = end;
	}

	@Override
	public String toString() {
		return "(" + start + "," + end + ')';
	}
}
